package features.advance.leetcode.math;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * 169. 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[3,2,3]
 * 输出：3
 * 示例 2：
 *
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 *
 *
 * 进阶：
 *
 * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 * @author LIN
 * @date 2022-03-30 11:21
 */
public class Solution169 {

    public static void main(String[] args) throws Exception {
        Solution solution = new Solution() {
        };

        int[] nums = {2,1,2,2,1};
        solution.majorityElement(nums);

        // 哈希表法

        Solution solution1 = new Solution() {
            @Override
            public int majorityElement(int[] nums) throws Exception {
                int res = nums[0];
                Map<Integer, Integer> map = new HashMap<>(16);
                int max = 0;
                for (int num : nums) {
                    if (map.containsKey(num)) {
                        int count = map.get(num) + 1;
                        map.put(num, count);
                        if (max < count) {
                            res = num;
                            max = count;
                        }
                    } else {
                        map.put(num, 1);
                    }
                }
                if(max <= nums.length /2){
                    throw new Exception("不存在多数元素");
                }
                return res;
            }
        };
        int res = solution1.majorityElement(nums);
        System.out.println(res);

        new Solution(){
            private Map<Integer, Integer> countNums(int[] nums) {
                Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
                for (int num : nums) {
                    if (!counts.containsKey(num)) {
                        counts.put(num, 1);
                    } else {
                        counts.put(num, counts.get(num) + 1);
                    }
                }
                return counts;
            }

            @Override
            public int majorityElement(int[] nums) {
                Map<Integer, Integer> counts = countNums(nums);

                Map.Entry<Integer, Integer> majorityEntry = null;
                for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
                    if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                        majorityEntry = entry;
                    }
                }

                return majorityEntry.getKey();
            }
        };

        // 排序方法
        new Solution(){
            class Solution {
                public int majorityElement(int[] nums) {
                    // O(n log(n))时间复杂度
                    Arrays.sort(nums);
                    return nums[nums.length / 2];
                }
            }
        };

    }

    static class Solution {
        /**
         * 定的数组总是存在多数元素，所以无需校验
         * @param nums
         * @return
         */
        public int majorityElement(int[] nums) throws Exception {
            if (nums == null || nums.length == 0) {
                return -1;
            }
            if(nums.length == 1){
                return nums[0];
            }
            int candidate = nums[0];
            int count = 1;

            for (int i = 1; i < nums.length; i++) {
                if(count == 0){
                    candidate = nums[i];
                }
                count += (candidate == nums[i])?-1:1;
            }
            return candidate;
        }
    }
}
